/**
 * @Author：ming
 * @Date：2023/9/29 3:43 PM
 * @Filename：Lc637
 */

import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.List;

/**
 * @author ming
 */
public class Lc637 {
    public List<Double> averageOfLevels(TreeNode root) {
        ArrayList<Double> doubles = new ArrayList<>();
        ArrayList<TreeNode> parent = new ArrayList<>();
        ArrayList<TreeNode> child = new ArrayList<>();

        if(root==null){
            return doubles;
        }
        parent.add(root);
        long sum = 0;
        int n = 0;
        while (parent.size()!=0){
            TreeNode p = parent.get(0);
            n++;
            sum += p.val;
            if(p.left!=null){
                child.add(p.left) ;
            }
            if(p.right!=null){
                child.add(p.right);
            }
            parent.remove(0);

            if(parent.size()==0){
                double i = (double) sum/(double) n;
                doubles.add(i);
                sum =0;
                n =0;
                if(child.size()==0){
                    break;
                }

                for (TreeNode q : child) {
                    parent.add(q);
                }
                child.clear();

            }
        }
        return doubles;
    }
}
